package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;
//46. 全排列
//
//给定一个没有重复数字的序列，返回其所有可能的全排列。
//
//示例:
//
//输入: [1,2,3]
//输出:
//[
//  [1,2,3],
//  [1,3,2],
//  [2,1,3],
//  [2,3,1],
//  [3,1,2],
//  [3,2,1]
//]

public class Solution046 {
	
	public List<List<Integer>> permute(int[] nums) {
        
		List<List<Integer>> res = new ArrayList<>();
		
		if (nums == null || nums.length == 0) {
			return res;
		}
		
		dfs(nums, new boolean[nums.length], res, new ArrayList<>());
		return res;
		
    }
	
	private void dfs(int[] nums, boolean[] mark, List<List<Integer>> res, List<Integer> path) {
		if (path.size() == nums.length) {
			res.add(new ArrayList<>(path));
			return;
		}
		
		for (int i=0; i<nums.length; i++) {
			if (mark[i]) {
				continue;
			}
			mark[i] = true;
			path.add(nums[i]);
			dfs(nums, mark, res, path);
			path.remove(path.size()-1);
			mark[i] = false;
		}
		
	}
	
	
}
